package 链表;

import java.util.concurrent.CompletableFuture;

public class No148排序链表 {

    /**
     * 在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。
     *
     * 示例 1:
     * 输入: 4->2->1->3
     * 输出: 1->2->3->4
     * 示例 2:
     * 输入: -1->5->3->4->0
     * 输出: -1->0->3->4->5
     * 在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。
     * 在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。
     */

    //回顾147的排序链表
    public static ListNode sortListNo147(ListNode head) {

        ListNode listNode=new ListNode();//放置排序好的节点
        ListNode pre=listNode;//前驱节点
        ListNode cur=head;//当前要比较的节点

        while (cur!=null){

            while (pre.next!=null&&pre.next.val<cur.val){
                //下一个节点是小于当前节点的,所以要继续遍历
                pre=pre.next;
            }

            ListNode next=cur.next;//记录下一个要遍历的节点

            //开始交换
            ListNode next2=pre.next;//保存插入节点的下一个节点

            pre.next=cur;

            cur.next=next2;

            cur=next;

            pre=listNode;
        }
        return listNode.next;
    }


    /**
     * 这里面的第一个评论不错;
     * https://leetcode-cn.com/problems/sort-list/solution/sort-list-gui-bing-pai-xu-lian-biao-by-jyd/
     */
    public ListNode sortList(ListNode head) {
        // 1、递归结束条件
        if (head == null || head.next == null) {
            return head;
        }

        // 2、找到链表中间节点并断开链表 & 递归下探
        //找到每次head的中间节点
        ListNode midNode = middleNode(head);
        //以中间节点切割
        ListNode rightHead = midNode.next;
        midNode.next = null;//让中间节点和后面的节点断开联系

        //继续切割子链表的中间节点
        ListNode left = sortList(head);

        //继续切割
        ListNode right = sortList(rightHead);

        //底层是单个元素拼接且向上回溯拼接,一定是有序的
        return mergeTwoLists(left, right);
    }

    //找到链表中间节点（876. 链表的中间结点）
    //找到了中间节点,那么就可以把问题最小化,把每个的中间节点都算出来
    private ListNode middleNode(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode slow = head;
        ListNode fast = head.next.next;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        return slow;
    }

    // 合并两个有序链表（21. 合并两个有序链表）
    private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode sentry = new ListNode(-1);
        ListNode curr = sentry;

        while(l1 != null && l2 != null) {
            if(l1.val < l2.val) {
                curr.next = l1;
                l1 = l1.next;
            } else {
                curr.next = l2;
                l2 = l2.next;
            }

            curr = curr.next;
        }

        curr.next = l1 != null ? l1 : l2;
        return sentry.next;
    }

    public static void main(String[] args) throws InterruptedException {
        int[] arr=new int[]{4,2,1,3};
    }

}
